package com.zhouhong.muke_leetcode_two;


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @ClassName: Algorithm-and-Data-Structure
 * @Description:
 * @Author: zhouhong
 * @Create: 2021-04-05 22:07
 **/

//给定一个二叉树，判断其是否是一个有效的二叉搜索树。
//
// 假设一个二叉搜索树具有如下特征：
//
//
// 节点的左子树只包含小于当前节点的数。
// 节点的右子树只包含大于当前节点的数。
// 所有左子树和右子树自身必须也是二叉搜索树。

public class LeetCode0098 {
    // 思路：二叉搜索树的中序遍历为有序
    // -----递归
    void dfs (ArrayList<Integer> res, TreeNode root) {
        if (root == null){
            return;
        }
        dfs(res, root.left);
        res.add(root.val);
        dfs(res, root.right);
    }
    public boolean isValidBST(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        dfs(list, root);
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) <= list.get(i - 1)){
                return false;
            }
        }
        return true;
    }






    //-------非递归
    public boolean isValidBST1(TreeNode root) {
        List<Integer>list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null){
            if (cur != null){
                stack.push(cur);
                cur = cur.left;
            }else {
                cur = stack.pop();
                list.add(cur.val);
                cur = cur.right;
            }
        }
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) <= list.get(i - 1)){
                return false;
            }
        }
        return true;
    }

}
